//https://leetcode.cn/problems/merge-two-sorted-lists/


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution 
{
public:
    //明确递归函数要做什么？
    //递归函数要将两个链表从小到大合并，返回当前链表的头
    //怎么处理？
    //比较大小，小的就是当前链表的头节点，下一个节点是下一次递归得来的头节点
    //如果有一个为空，那么另一个链表就是当前两个链表的头
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        if(!list1) return list2;
        if(!list2) return list1;

        if(list1->val<list2->val)
        {
            list1->next =_mergeTwoLists(list1->next,list2);
            return list1;
        }
        else 
            list2->next =_mergeTwoLists(list1,list2->next);
        return list2;
    }
};